package im.oen.boot.common.utils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Kevin.Xu
 */
public class Similarity {

    /**
     * 余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。
     * 0 度角的余弦值是 1，而其他任何角度的余弦值都不大于 1；并且其最小值是-1。
     * 从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。
     * 两个向量有相同的指向时，余弦相似度的值为 1；两个向量夹角为 90°时，余弦相似度的值为 0；
     * 两个向量指向完全相反的方向时，余弦相似度的值为-1。这结果是与向量的长度无关的，仅仅与向量的指向方向相关。
     * 余弦相似度通常用于正空间，因此给出的值为 0 到 1 之间。
     *
     * @param a 字符串A
     * @param b 字符串B
     * @return 相似度
     */
    public static float cos(String a, String b) {
        if (a == null || b == null) {
            return 0F;
        }
        Set<Integer> aChar = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChar = b.chars().boxed().collect(Collectors.toSet());

        // 统计字频
        Map<Integer, Integer> aMap = new HashMap<>(aChar.size());
        Map<Integer, Integer> bMap = new HashMap<>(bChar.size());
        for (Integer a1 : aChar) {
            aMap.put(a1, aMap.getOrDefault(a1, 0) + 1);
        }
        for (Integer b1 : bChar) {
            bMap.put(b1, bMap.getOrDefault(b1, 0) + 1);
        }

        // 向量化
        Set<Integer> union = union(aChar, bChar);
        int[] aVec = new int[union.size()];
        int[] bVec = new int[union.size()];
        List<Integer> collect = new ArrayList<>(union);
        for (int i = 0; i < collect.size(); i++) {
            aVec[i] = aMap.getOrDefault(collect.get(i), 0);
            bVec[i] = bMap.getOrDefault(collect.get(i), 0);
        }

        // 分别计算三个参数
        int p1 = 0;
        for (int i = 0; i < aVec.length; i++) {
            p1 += (aVec[i] * bVec[i]);
        }

        float p2 = 0f;
        for (int i : aVec) {
            p2 += (i * i);
        }
        p2 = (float) Math.sqrt(p2);

        float p3 = 0f;
        for (int i : bVec) {
            p3 += (i * i);
        }
        p3 = (float) Math.sqrt(p3);

        return ((float) p1) / (p2 * p3);
    }

    /**
     * 汉明距离是编辑距离中的一个特殊情况，仅用来计算两个等长字符串中不一致的字符个数。
     *
     * @param a 字符串A
     * @param b 字符串B
     * @return 相似度
     */
    public static float hamming(String a, String b) {
        if (a == null || b == null) {
            return 0f;
        }
        if (a.length() != b.length()) {
            return 0f;
        }

        int disCount = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                disCount++;
            }
        }
        return (float) disCount / (float) a.length();
    }

    /**
     * 莱文斯坦距离，又称 Levenshtein 距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
     *
     * @param a 字符串A
     * @param b 字符串B
     * @return 相似度
     */
    public static float levenshtein(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        if (a == null || b == null) {
            return 0F;
        }
        int editDistance = editDis(a, b);
        return 1 - ((float) editDistance / Math.max(a.length(), b.length()));
    }

    /**
     * Sorensen Dice 相似度系数
     * The Sørensen–Dice coefficient (see below for other names) is a statistic used to gauge the similarity of two samples.
     * It was independently developed by the botanists Thorvald Sørensen[1] and Lee Raymond Dice,[2] who published in 1948 and 1945 respectively.
     *
     * @param a 字符串A
     * @param b 字符串B
     * @return 相似度
     */
    public static float sorensenDice(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        if (a == null || b == null) {
            return 0F;
        }
        Set<Integer> aChars = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChars = b.chars().boxed().collect(Collectors.toSet());
        // 求交集数量
        int intersect = intersection(aChars, bChars).size();
        if (intersect == 0) {
            return 0F;
        }
        // 全集，两个集合直接加起来
        int aSize = aChars.size();
        int bSize = bChars.size();
        return (2 * (float) intersect) / ((float) (aSize + bSize));
    }

    /**
     * The Jaccard index, also known as Intersection over Union and the Jaccard similarity coefficient
     * (originally given the French name coefficient de communauté by Paul Jaccard),
     * is a statistic used for gauging the similarity and diversity of sample sets.
     * The Jaccard coefficient measures similarity between finite sample sets,
     * and is defined as the size of the intersection divided by the size of the union of the sample sets:
     *
     * @param a 字符串A
     * @param b 字符串B
     * @return 相似度
     */
    public static float jaccard(String a, String b) {
        if (a == null && b == null) {
            return 1f;
        }
        // 都为空相似度为 1
        if (a == null || b == null) {
            return 0f;
        }
        Set<Integer> aChar = a.chars().boxed().collect(Collectors.toSet());
        Set<Integer> bChar = b.chars().boxed().collect(Collectors.toSet());
        Set<String> result = new HashSet<String>();
        // 交集数量
        int intersection = intersection(aChar, bChar).size();
        if (intersection == 0) {
            return 0;
        }
        // 并集数量
        int union = union(aChar, bChar).size();
        return ((float) intersection) / (float) union;
    }

    /**
     * 交集
     *
     * @param a
     * @param b
     * @return
     */
    private static Set intersection(Set a, Set b) {
        Set res = new HashSet();
        res.addAll(a);
        res.retainAll(b);
        return res;
    }

    /**
     * 合集
     *
     * @param a
     * @param b
     * @return
     */
    private static Set union(Set a, Set b) {
        Set res = new HashSet();
        res.addAll(a);
        res.addAll(b);
        return res;
    }

    /**
     * 差集
     *
     * @param a
     * @param b
     * @return
     */
    private static Set difference(Set a, Set b) {
        Set res = new HashSet();
        res.addAll(a);
        res.removeAll(b);
        return res;
    }

    private static int editDis(String a, String b) {

        int aLen = a.length();
        int bLen = b.length();

        if (aLen == 0) {
            return aLen;
        }
        if (bLen == 0) {
            return bLen;
        }

        int[][] v = new int[aLen + 1][bLen + 1];
        for (int i = 0; i <= aLen; ++i) {
            for (int j = 0; j <= bLen; ++j) {
                if (i == 0) {
                    v[i][j] = j;
                } else if (j == 0) {
                    v[i][j] = i;
                } else if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    v[i][j] = v[i - 1][j - 1];
                } else {
                    v[i][j] = 1 + Math.min(v[i - 1][j - 1], Math.min(v[i][j - 1], v[i - 1][j]));
                }
            }
        }
        return v[aLen][bLen];
    }
}
